/**
 * 
 */
package com.gwcloud.leetcode.hot100;

import java.util.ArrayList;

import com.gwcloud.leetcode.common.datastructure.ListNode;

/**
 * @ClassName   : Leetcode234 
 * @author      : ganwei 
 * @date        : 2020年5月1日
 * @Description : Leetcode234 回文链表
 */
public class Leetcode0234 {
	/**
	 * -解题思路，转数组，双指针校验，但空间复杂度为O(N)
	 */
    public static boolean isPalindrome(ListNode head) {
    	ArrayList<Integer> list = new ArrayList<Integer>();
    	ListNode indexA = head;
    	while(indexA != null) {
    		list.add(indexA.val);
    		indexA = indexA.next;
    	}
    	
    	int front = 0,tail = list.size()-1;
    	
    	while(front<tail) {
    		
    		if(!list.get(front).equals(list.get(tail))) {
    			return false;
    		}
    		front++;
    		tail--;
    	}
    	
    	return true;
    }
    
    /**
     * -解题思路,需将空间复杂度降为O(1)
     * -找到前半部分链表的尾节点
     * -反转后半部分链表
     * -判断是否为回文
     * -恢复链表
     * -返回结果
     */
    public static boolean isPalindrome_1(ListNode head) {
    	
    	return false;
    }
    
    public static void main(String args[]){
    	ListNode n1 = new ListNode(1);
    	ListNode n2 = new ListNode(2);
    	ListNode n3 = new ListNode(2);
    	ListNode n4 = new ListNode(1);
    	n1.next = n2;
    	n2.next = n3;
    	n3.next = n4;

    	System.out.println(isPalindrome(n1));
    }
}
